๐Ÿ‘ฉโ€๐Ÿ’ป 60061. ๊ธฐ๋‘ฅ๊ณผ ๋ณด ์„ค์น˜

@Seongukbaek Posted June 23, 2022 ยท Updated June 23, 2022 ยท 4 min read

๋ฌธ์ œ

Programmers - ๊ธฐ๋‘ฅ๊ณผ ๋ณด ์„ค์น˜

๐Ÿ“ Logic

private static boolean checkPillar(int x, int y) { // ๋ฐ”๋‹ฅ ์„ค์น˜ if (y == 0) return true; // ์•„๋ž˜์— ๊ธฐ๋‘ฅ์ด ์žˆ๋Š” ๊ฒฝ์šฐ else if (y > 0 && pillars[x][y - 1]) return true; // ํ•œ์ชฝ์— ๋ณด๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ else return x > 0 && covers[x - 1][y] || covers[x][y]; } private static boolean checkCover(int x, int y) { // ํ•œ์ชฝ ๋์— ๊ธฐ๋‘ฅ์ด ์žˆ๋Š” ๊ฒฝ์šฐ if (y > 0 && pillars[x][y - 1] || pillars[x + 1][y - 1]) return true; // ์–‘์ชฝ ๋์ด ๋ชจ๋‘ ๋ณด์™€ ์—ฐ๊ฒฐ๋œ ๊ฒฝ์šฐ else return x > 0 && covers[x - 1][y] && covers[x + 1][y]; } private static boolean canDelete(int n) { for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) // ๊ธฐ๋‘ฅ์ด ํ•ด๋‹น ์œ„์น˜์— ์žˆ์„ ์ˆ˜ ์—†๊ฑฐ๋‚˜, ๋ณด๊ฐ€ ํ•ด๋‹น ์œ„์น˜์— ์žˆ์„ ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ false if ((pillars[i][j] && !checkPillar(i, j)) || (covers[i][j] && !checkCover(i, j))) return false; return true; }
  • checkPillar ์™€ checkCover ๋Š” ๊ฐ๊ฐ ๊ธฐ๋‘ฅ๊ณผ ๋ณด๊ฐ€ ์„ค์น˜๊ฐ€๋Šฅํ•œ์ง€๋ฅผ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜์ด๋‹ค.

    • ์ฃผ์–ด์ง„ ์กฐ๊ฑด์— ๋”ฐ๋ผ ์ด๋ฅผ ํ™•์ธํ•œ๋‹ค.
  • canDelete ๋Š” ๊ธฐ๋‘ฅ๊ณผ ๋ณด๋ฅผ ์ฃผ์–ด์ง„ ๋ช…๋ น๋Œ€๋กœ ์‚ญ์ œํ–ˆ์„ ๋•Œ, ์ฃผ์–ด์ง„ ์กฐ๊ฑด์„ ๋ถˆ๋งŒ์กฑํ•˜๋Š” ์ขŒํ‘œ๊ฐ€ ์—†๋Š”์ง€ ํ™•์ธํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Solution { static boolean[][] pillars; static boolean[][] covers; public int[][] solution(int n, int[][] build_frame) { pillars = new boolean[n + 1][n + 1]; covers = new boolean[n + 1][n + 1]; int count = 0; for (int[] bf : build_frame) { int x = bf[0]; int y = bf[1]; int struct = bf[2]; int command = bf[3]; // ๊ธฐ๋‘ฅ if (struct == 0) { // ์‚ญ์ œ if (command == 0) { pillars[x][y] = false; if (!canDelete(n)) pillars[x][y] = true; else count--; } // ์„ค์น˜ else { if (!checkPillar(x, y)) continue; pillars[x][y] = true; count++; } } // ๋ณด else { // ์‚ญ์ œ if (command == 0) { covers[x][y] = false; if (!canDelete(n)) covers[x][y] = true; else count--; } // ์„ค์น˜ else { if (!checkCover(x, y)) continue; covers[x][y] = true; count++; } } } int[][] answer = new int[count][3]; int idx = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (pillars[i][j]) answer[idx++] = new int[]{i, j, 0}; if (covers[i][j]) answer[idx++] = new int[]{i, j, 1}; } } return answer; } private static boolean checkPillar(int x, int y) { // ๋ฐ”๋‹ฅ ์„ค์น˜ if (y == 0) return true; // ์•„๋ž˜์— ๊ธฐ๋‘ฅ์ด ์žˆ๋Š” ๊ฒฝ์šฐ else if (y > 0 && pillars[x][y - 1]) return true; // ํ•œ์ชฝ์— ๋ณด๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ else return x > 0 && covers[x - 1][y] || covers[x][y]; } private static boolean checkCover(int x, int y) { // ํ•œ์ชฝ ๋์— ๊ธฐ๋‘ฅ์ด ์žˆ๋Š” ๊ฒฝ์šฐ if (y > 0 && pillars[x][y - 1] || pillars[x + 1][y - 1]) return true; // ์–‘์ชฝ ๋์ด ๋ชจ๋‘ ๋ณด์™€ ์—ฐ๊ฒฐ๋œ ๊ฒฝ์šฐ else return x > 0 && covers[x - 1][y] && covers[x + 1][y]; } private static boolean canDelete(int n) { for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) // ๊ธฐ๋‘ฅ์ด ํ•ด๋‹น ์œ„์น˜์— ์žˆ์„ ์ˆ˜ ์—†๊ฑฐ๋‚˜, ๋ณด๊ฐ€ ํ•ด๋‹น ์œ„์น˜์— ์žˆ์„ ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ false if ((pillars[i][j] && !checkPillar(i, j)) || (covers[i][j] && !checkCover(i, j))) return false; return true; } }

โœ๏ธ Review

  • ์ฒ˜์Œ ๊ตฌํ˜„ ์‹œ, ๊ธฐ๋‘ฅ๊ณผ ๋ณด์˜ ์‚ญ์ œ ์กฐ๊ฑด ํ™•์ธ๋•Œ๋ฌธ์— ์• ๋ฅผ ๋จน์—ˆ๊ณ , map ํ•˜๋‚˜์— ๊ธฐ๋‘ฅ ์—ฌ๋ถ€์™€ ๋ณด ์—ฌ๋ถ€๋ฅผ ํ•จ๊ป˜ ์ €์žฅํ–ˆ์—ˆ๋Š”๋ฐ, ์ƒ๊ฐํ•ด๋ณด๋‹ˆ ๊ธฐ๋‘ฅ๊ณผ ๋ณด๊ฐ€ ํ•œ ์ขŒํ‘œ์— ํ•จ๊ป˜ ์กด์žฌํ•  ์ˆ˜ ์žˆ์—ˆ๋˜ ๊ฒƒ์„ ๊ฐ„๊ณผํ–ˆ์—ˆ๋‹ค.
  • ๋˜ํ•œ, ์„ค์น˜์™€ ์‚ญ์ œํ•˜๋Š” ๊ตฌ์กฐ๋ฌผ์— ๋Œ€ํ•œ ArrayList ๋ฅผ ๋งŒ๋“ค์–ด์„œ ๊ด€๋ฆฌํ•  ๊ตฌ์กฐ๋ฌผ์˜ ๋ฒ”์œ„๋ฅผ ์ค„์ด๋ ค ํ–ˆ๋Š”๋ฐ ๊ตฌํ˜„์—์„œ ์กฐ๊ธˆ ๋ง‰ํ˜”๋‹ค ...

    • ์ƒˆ ๊ฐ์ฒด๋ฅผ ๋งŒ๋“ค์–ด์„œ ์ด๋ฏธ ์žˆ๋Š” Map ์—์„œ ๊ฐ’์„ ์กฐํšŒํ•˜๋ คํ•˜๋‹ˆ ์•„์˜ˆ ๋‹ค๋ฅธ ๊ฐ์ฒด๋กœ ํŒ๋‹จ์„ ํ•ด์„œ ์กฐํšŒ๊ฐ€ ๋ถˆ๊ฐ€๋Šฅํ–ˆ๋‹ค.
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€